public class QuickSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 5, 5, 3, 2, 1, 2, 4};
        int start = 0, end = arr.length - 1;
        quickSort(arr, start, end);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int start, int end) {
        if (arr.length < 1 || start >= end)
            return;

        //定义临时指针，因为 start，end在递归中会用到，所以不能被修改。
        int left = start, right = end;
        //定义基准值
        int pivot = left, pivotVal = arr[pivot];

        while (left != right) {
            //1、从右开始，找到比 pivotVal 小的元素即 停止
            while (left < right && pivotVal < arr[right]) {
                right--;
            }
           
            //2、从「 左 」开始，找到比 pivotVal 大的元素即 停止
            // 这里注意   arr[pivot] >= arr[left]，需要加等于。不然当有重复值的时候，会进入死循环。
            // 而且会导致遗漏元素
            while (left < right && pivotVal >= arr[left]) {
                left++;
            }
            
            //3、 交换找到的两个元素，进行位置互换
            if (left < right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
            }
        }
        //4、 将基准值的下标更新到 正确的位置，即保证，新的下标左侧的小于基准值， 右侧的大于基准值
        arr[pivot] = arr[left];
        arr[left] = pivotVal;
        //5、排序 左侧数组
        quickSort(arr, start, left - 1);
        //5、排序 右侧数组
        quickSort(arr, right + 1, end);

    }
}